package leetcode_1_20;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class fourSum_18 {
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length,
        lastnum=Integer.MIN_VALUE;
        //当前数组的长度为空，或者长度小于4时，直接退出
        if (nums == null || len < 4) {
            return res;
        }
        //将数组进行排序
        Arrays.sort(nums);
        //遍历数组中的每一个元素
        for (int i = 0; i < len - 3; i++) {
            //去重，当起始的值等于前一个元素，那么得到的结果将会和前一次相同
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int t=i+1; t < len-2 ; t++) {
                if (t  > 1 && nums[t] ==lastnum)
                    continue;
                //如果起始元素与后3位之和大于target ，就直接退出
                if ((long)nums[i] + nums[t] +nums[i + 2] + nums[i + 3] > target) {
                    break;
                }
                int l = t + 1;
                int r = len - 1;
                while (l < r) {
                    long sum = (long)nums[i]+nums[t] +nums[l] + nums[r];
                    if (sum == target) {
                        res.add(Arrays.asList(nums[i], nums[t],nums[l], nums[r]));
                        //在将左指针和右指针移动的时候，先对左右指针的值，进行判断
                        //如果重复，直接跳过。
                        //去重，因为 i 不变，当此时 l取的数的值与前一个数相同，所以不用在计算，直接跳
                        while (l < r && nums[l] == nums[ l + 1]) {
                            l++;
                        }
                        //去重，因为 i不变，当此时 r 取的数的值与前一个相同，所以不用在计算
                        while (l < r && nums[r] == nums[r - 1]) {
                            r--;
                        }
                        //将 左指针右移，将右指针左移。
                        l++;
                        r--;
                        //如果结果小于target，将左指针右移
                    } else if (sum < target) {
                        l++;
                        //如果结果大于target，将右指针左移
                    } else if (sum > target) {
                        r--;
                    }
                }
                lastnum=nums[t];
            }
            lastnum=Integer.MIN_VALUE; //完整循环经过一轮后，重置lastnum
        }
        return res;
    }
}
